/**
 * Created by L.jp
 * Description:输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输
 * 入的数组的任意两个数字都互不相同。
 * User: 86189
 * Date: 2021-12-25
 * Time: 15:39
 */
//根据二叉搜索树性质可以将后序序列数组分为三部分，分别是左子树、右子树、根节点，并且满足整体值左<根<右
    //如果要判断一个序列是否是二叉搜索树的后序遍历序列，那么就要左右子树都要满足二叉搜索树的性质，即对于数组的三个区间的划分都要满足二叉搜索树性质
    //其实这是一个递归操作，对 于子树的子树又可以这样分为三个部分进行判断
    //二叉搜索树的后序遍历从小到大排序后就是中序遍历
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null || sequence.length==0){
            return false;
        }
        //一开始就需要从0到len-1的区间确定左右子树
        //递归去判断每一课子树是不是二叉搜索树，实际就是不断缩小范围知道start==end
        return  VerifySquenceOfBSTHelper(sequence,0,sequence.length-1);
    }
    public boolean VerifySquenceOfBSTHelper(int[] sequence,int start,int end){
        //范围不断减小，直到只有一个节点，此时start会等于end，start就代表左树的第一个节点，end就是根节点，当只有一个节点时，start就==end
        if(start>=end){
            return true;
        }
        //取出根节点，用于比较
       int root=sequence[end];
       //先找到左子树部分，然后遍历
       int i=start;
       while(i<end && sequence[i]<root){
           i++;
       }
       //此时左子树区间为start~i-1
       //到了这里说明找到了左子树部分，此时i所在的位置就是右子树的第一个，还需要确定右子树的区间
        for(int j=i;j<end;j++){
            if(sequence[j]<root){
                return false;
            }
        }
        //此时找到了右子树区间，为i~j
        //走到这里并不能确定这个就是二叉搜索树，还需要再遍历左右子树的子树区间才可以确定，那么同样也是这么判断,所以递归
        return VerifySquenceOfBSTHelper(sequence,start,i-1) && VerifySquenceOfBSTHelper(sequence,i,end-1);
    }
}
